package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0078.%E5%AD%90%E9%9B%86.md#78%E5%AD%90%E9%9B%86
 * <p>
 * 78.子集
 * 力扣题目链接
 * <p>
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
 */
public class SCode78 {


    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> ret = combine(nums);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<Integer>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    public static List<List<Integer>> combine(int[] nums) {
        backtracking(nums, 0);
        return ret;
    }


    public static void backtracking(int[] nums, int startIndex) {
        //这是因为每个元素都可以单独成一个子集，然后自己再跟别人构成自己
        /**
         * [1,2,3]
         * [1]
         * [1] &[2,3] ->[1,2]、[1,3]-> [1,2,3]
         */
        ret.add(new ArrayList<>(temp));
        int len = nums.length;
        if (startIndex > len) {
            return;
        }

        for (int i = startIndex; i < len; i++) {
            int cur = nums[i];
            temp.add(cur);
            backtracking(nums, i + 1);
            temp.remove(temp.size() - 1);
        }

    }


}
